// 1_1The longest substring without repeated characters.cpp : Defines the entry point for the console application.
//给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
/*
示例 1:
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。*/

#include "stdafx.h"
#include<iostream>

using namespace std;

int length(char *s)
{
	int m=0;
	while(*s!='\0'){
		s++;
		m++;
	}
	return m;
}

int maxlength(char *s)
{
	int n=length(s);int gg;
	int start[10000];int end[10000];int judge[10000];
	for(int i=0;i<n-1;i++){
		for(int j=i+1;j<n;j++){
			gg=((2*n-i-1)*i)/2+j-i;
			judge[((2*n-i-1)*i)/2+j-i]=1;
			start[((2*n-i-1)*i)/2+j-i]=i;
			end[((2*n-i-1)*i)/2+j-i]=j;//内部的数据为第{（2n-i-1）i}/2+j-i组；共计n(n-1)/2组；
		//	cout<<gg<<endl;
			for(int u=i;u<=j;u++){
				for(int v=u+1;v<=j;v++){
					if(*(s+u)==*(s+v)){
						judge[((2*n-i-1)*i)/2+j-i]=0;
					}
				}
			}
			cout<<start[((2*n-i-1)*i)/2+j-i]<<"  "<<end[((2*n-i-1)*i)/2+j-i]<<"  "<<judge[gg]<<endl;//该行进行判断检测
		}
	}
	int p=end[0]-start[0];int q;int judgezero=0;
	for(int k=1;k<=n*(n-1)/2;k++){
		if(judge[k]==1){
			if(p<end[k]-start[k]){
				p=end[k]-start[k];
				q=k;
			}
		}
		judgezero=judgezero+judge[k];
//		cout<<start[k]<<" "<<end[k]<<" ";
//		cout<<judgezero;
	}
//	cout<<q;
	int rr;
	if(judgezero==0){
		cout<<"无重复字符的最长子串是:"<<s[0]<<endl;
		rr=1;
	}
	else{
			cout<<"max:from "<<start[q]<<" to "<<end[q]<<endl<<"无重复字符的最长子串是:";
			for(int jj=start[q];jj<=end[q];jj++){
			cout<<s[jj];
			}
			cout<<endl/*<<"其长度为:"<<end[q]-start[q]+1<<endl*/;
			rr=end[q]-start[q]+1;
		}
	return rr;
}

void main()
{
	char s[]="bbbbbb";
	int m=maxlength(s);
	cout<<"其长度为:"<<m<<endl;
}

// FIXME: 
//  1. 你的测试数据比较简单，需要用多个测试数据测试程序是正确的
//  2. 到数据结构的练习，需要多考虑边界条件、特殊情况，在基本程序写完之后，多想想如何测试程序，是否存在隐藏的Bug
